package primary.primary0;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class S0018四数之和 {

    /**
     * 答案，主要看下对于重复数值的处理逻辑
     * 这里巧妙地通过跳过重复值，省略了去重的逻辑
     */
    class Solution2 {
        public List<List<Integer>> fourSum(int[] nums, int target) {
            List<List<Integer>> quadruplets = new ArrayList<List<Integer>>();
            if (nums == null || nums.length < 4) {
                return quadruplets;
            }
            Arrays.sort(nums);
            int length = nums.length;
            for (int i = 0; i < length - 3; i++) {
                // 如果等于上一个数，就跳过
                if (i > 0 && nums[i] == nums[i - 1]) {
                    continue;
                }
                if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
                    break;
                }
                // 如果当前值和后面三个最大的加起来还不够，那也跳过
                if ((long) nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target) {
                    continue;
                }
                for (int j = i + 1; j < length - 2; j++) {
                    // 这里也在跳过
                    if (j > i + 1 && nums[j] == nums[j - 1]) {
                        continue;
                    }
                    if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
                        break;
                    }
                    // 也在先看下最大case是不是不够
                    if ((long) nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) {
                        continue;
                    }
                    int left = j + 1, right = length - 1;
                    while (left < right) {
                        long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                        if (sum == target) {
                            // 是会找到多个值的，所以不能遇到一个就停
                            quadruplets.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                            // 跳过重复的
                            while (left < right && nums[left] == nums[left + 1]) {
                                left++;
                            }
                            left++;
                            while (left < right && nums[right] == nums[right - 1]) {
                                right--;
                            }
                            // 逮到一个命中的之后，左右都往中间移
                            right--;
                        } else if (sum < target) {
                            // 这里倒没去重，实际上如果一样的话，会再回来再执行一次
                            left++;
                        } else {
                            right--;
                        }
                    }
                }
            }
            return quadruplets;
        }
    }



    class Solution1 {
        /**
         * 5
         * 因为不要求顺序，只要数字，然后这个数字，nums里面是可以重复的
         * 考虑排序后枚举两个数字，然后另外两个用双指针
         * 另外两个数值为什么可以这样，可以参考 S1009排序矩阵查找 和 S0240搜索二维矩阵II，总之就是每一次操作相当于抹掉了一列/一行数据，
         * 三数之和就是这么写的
         */
        public List<List<Integer>> fourSum(int[] nums, int target) {
            Arrays.sort(nums);
            List<List<Integer>> res = new ArrayList<>();
            for (int a = 0; a < nums.length; a++) {
                for (int b = a + 1; b < nums.length; b++) {
                    int c = b + 1;
                    int d = nums.length - 1;
                    while (c < d) {
                        // 这个0L是为了防止多个10^9相加导致溢出
                        if (0L + nums[a] + nums[b] + nums[c] + nums[d] > target) {
                            d--;
                            // 直接人肉转long，也不赖
                        } else if ((long) nums[a] + nums[b] + nums[c] + nums[d] < target) {
                            c++;
                        } else {
                            List<Integer> resEle = new ArrayList<>();
                            resEle.add(nums[a]);
                            resEle.add(nums[b]);
                            resEle.add(nums[c]);
                            resEle.add(nums[d]);
                            // 这里做个去重判断，和上一个做比较不行，因为中间可能会有重复的，所以要和每一个做比较，或者最后排序一下去重
                            boolean hasSame = false;
                            for (List<Integer> temp : res) {
                                // mark: 这里看了好久看不出问题，因为这里必须是equals，不能用==
                                if (temp.get(0).equals(resEle.get(0)) && temp.get(1).equals(resEle.get(1)) && temp.get(2).equals(resEle.get(2)) && temp.get(3).equals(resEle.get(3))) {
                                    hasSame = true;
                                    System.out.println(temp);
                                }
                            }
                            if (!hasSame) {
                                res.add(resEle);
                            }
                            // 一定要保证c＋＋，如果break的话会漏，没有c＋＋的话会死循环
                            c++;
                        }
                    }
                }
            }
            // 咋去重快？

            return res;
        }
    }
}
